package DMSXL._2024.BinaryTrees;

public class buildTreepre {
    public static void main(String[] args) {

    }
    public TreeNode buildTree(int[] inorder, int[] preorder) {
        return bulid(inorder,0, inorder.length,preorder , 0, preorder.length);
    }
    public TreeNode bulid(int[] inorder,int inBegin, int inEnd,  int[] preorder, int preBegin, int preEnd){
        if(inBegin >= inEnd || preBegin >= preEnd){
            return null;
        }
        int inIndex = find(inorder,preorder[preBegin]);
        TreeNode root = new TreeNode(preorder[inIndex]);
        int inLen = inIndex - inBegin;

        root.left = bulid(inorder,inBegin,inIndex,preorder,preBegin + 1,preBegin + inLen + 1);
        root.right = bulid(inorder,inIndex + 1,inEnd,preorder,preBegin + 1 + inLen, preEnd);

        return root;
    }
    //从inorder中找到位置
    public int find(int[] inorder, int value){
        for (int i = 0; i < inorder.length; i++) {
            if(value == inorder[i]){
                return i;
            }
        }
        return 0;
    }
}
